/*
 * Copyright (c) 2018-2024 北京华恒盛世科技有限公司
 * QUICKPOOL is licensed under Mulan PSL v2.
 * You can use this software according to the terms and conditions of the Mulan PSL v2.
 * You may obtain a copy of Mulan PSL v2 at:
 *     http://license.coscl.org.cn/MulanPSL2
 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
 * EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
 * MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
 * See the Mulan PSL v2 for more details.
*/

#include "js.h"

#ifdef __cplusplus
extern "C" {
#endif

struct jobRemainTime {
    int remain_time;
    int num_slot;
};

struct reservation {
    LIST_T *forw;
    LIST_T *back;
    struct job *backfillee_job;
    unsigned int node_index;
    int num_bf_slot;
    unsigned int num_bf_node;
    struct executeNode *bf_nodes;
};

struct backfillReadyNode {
    unsigned int total_slot;
    unsigned int number_free_slot;
    unsigned int node_index;
    LIST_T *bfjob_list;
};

static int compare_lefttime(const void *, const void *);
static void order_reservation_job(struct job *, LIST_T *, time_t);
static struct reservation *dup_backfillee(struct reservation *);
static int isin_backfill_readynode(struct backfillReadyNode *, unsigned int, unsigned int);
static void rm_backfill_slot(struct job *);

/**
 * @brief       policy: check if make reservation for job or not
 *
 * @param[in]   schedjob     #1: job to be checked
 * @param[in]   sessiontime  #2: schedule begin time
 * @param[out]  moveon       #3: tell caller to ignore the job for one session
 *
 * @note        This function should be called at the beginning of a schedule session.
 *              If job reservation time expires, do not schedule it for one session
 *              to let other jobs go.
 */
void
reservation_check(struct job *schedjob, time_t sessiontime, bool_t *moveon)
{
    *moveon = TRUE;

    if (!(schedjob->job_status & JOB_STATUS_RESERVE)) {

        schedjob->reserve_time = 0;
        return;
    }

    if ((0 < schedjob->job_queue->reservation_time && 0 < schedjob->reserve_time
         && sessiontime - schedjob->reserve_time > schedjob->job_queue->reservation_time)) {

        free_reserve_node(schedjob);
        schedjob->reserve_time = 0;

        schedjob->processed |= JOB_STAGE_READY;
        *moveon = FALSE;

        return;

    }

    free_reserve_node(schedjob);

    return;
} // end function reservation_check

/**
 * @brief       policy: reserve/release memory for a job
 *
 * @param[in]   rsvjob     #1: reservation job
 * @param[in]   op         #2: 1 or -1 to reserve or release memory
 *
 * @note        If job has memory request, do reserve/release memory for the job.
 */
void
reserve_memory_4job(struct job *rsvjob, int op)
{
    if (NULL == rsvjob->shared->job_req) {
        return;
    }

    if (NULL == rsvjob->start_info) {
        return;
    }

    struct requirement *req;
    req = get_merged_req(rsvjob->shared->job_req, rsvjob->job_queue->queue_req);
    if (NULL == req) {
        return;
    }

    /* Currently we do not support the memory reservation with rusage || syntax. */
    if (1 < LIST_NUM_ENTS(rsvjob->shared->job_req->req_list)) {
        return;
    }

    int on;
    TEST_BIT(MEM, req->rusage_bit_map, on);
    if (on == 0) {
        return;
    }

    unsigned int i;
    for (i = 0; i < rsvjob->start_info->number_exec_node; i++) {

        struct node *execNode = rsvjob->start_info->exec_nodes[i].enode;
        if (op == 1 && req->val[MEM] > execNode->load[MEM]) { // reserve nothing
            continue;
        }

        execNode->load[MEM] = execNode->load[MEM] - req->val[MEM] * op;
    }

    return;
} // end function reserve_memory_4job

/**
 * @brief       policy: reserve slot and memory for the job
 *
 * @param[in]   rsvjob     #1: reservation job
 *
 * @note        Job has not enough slot to go, make reservation for the job.
 */
void
reserve_4job(struct job *rsvjob)
{
    if (NULL == rsvjob->start_info) {
        return;
    }

    if (0 >= rsvjob->start_info->number_exec_node) {
        return;
    }

    char strJobId[32];
    if (rsvjob->job_status & JOB_STATUS_RESERVE) {
        log_message(ERR, NOCLASS, "%s: Job %s already has slots reserved before.",
                    __func__, jobid_2string(rsvjob->jobid, strJobId));

        return;
    }

    if (0 == rsvjob->reserve_time) {
        rsvjob->reserve_time = time(NULL);
    }

    update_reservation_account(rsvjob, rsvjob->job_status | JOB_STATUS_RESERVE);
    rsvjob->job_status |= JOB_STATUS_RESERVE;

    unsigned int i;
    for (i = 0; i < rsvjob->start_info->number_exec_node; i++) {

        if (!(qAttributes & QUEUE_POLICY_BACKFILL)) {
            rsvjob->job_queue->num_free_slot -= rsvjob->start_info->exec_nodes[i].number_slot;
        }

        if (gf_get_logclass() & SCHEDULE) {
            log_message(DEBUG2, SCHEDULE, "%s: Reserve slot on node %s for job %s.",
                        __func__, rsvjob->start_info->exec_nodes[i].enode->node_name,
                        jobid_2string(rsvjob->jobid, strJobId));
        }
    }

    if (rsvjob->job_queue->schedule_policy & QUEUE_POLICY_MEM_RESERVE) {
        reserve_memory_4job(rsvjob, 1);
    }

    return;
} // end function reserve_4job

/**
 * @brief       policy: set possible start time for a reservation job
 *
 * @param[in]   reservejob     #1: reservation job
 * @param[in]   sessiontime    #2: schedule begin time
 *
 * @note        Backill job can backfill slots from the job who has possible start time.
 */
void
setjob_starttime(struct job *reservejob, time_t sessiontime)
{
    char strJobId[32];
    if (gf_get_logclass() & SCHEDULE) {
        log_message(DEBUG2, SCHEDULE, "%s: trying to set start time to job %s",
                    __func__, jobid_2string(reservejob->jobid, strJobId));
    }

    reservejob->possible_start = 0;

    int needed;
    needed = reservejob->shared->submit.num_job_slot - reservejob->num_dispatch_slot;
    if (needed <= 0) {
        return;
    }

    unsigned int tableSize, totalRunJobs = 0;
    tableSize = 5 * needed;

    int eligible;
    eligible = 0;

    struct jobRemainTime *runlimitJob;
    runlimitJob = (struct jobRemainTime *)calloc(tableSize, sizeof(struct jobRemainTime));
    if (NULL == runlimitJob) {
        log_message(ERR, NOCLASS, STR_FUNC_D_FAIL_M, __func__,
                    "calloc", tableSize*sizeof(struct jobRemainTime));
        return;
    }

    int num;
    unsigned int i;

    struct node *ndata;
    HASH_WALK_T walk;
    char *key;
    gf_hash_walk_start(ghashHost, &walk);
    while (NULL != (ndata = (struct node *)gf_hash_walk(&walk, &key))) {

        if ((ndata->node_tag & HOST_LOST_FOUND) || (ndata->node_tag & HOST_DUMMY_ALL)) {
            continue;
        }

        if (0 == LIST_NUM_ENTS(ndata->started_jobs)) {
            continue;
        }

        for (i = 0; i < reservejob->num_ready_node; i++) {
            if (ndata == reservejob->ready_nodes[i].rnode) {
                break;
            }
        }

        if (i >= reservejob->num_ready_node) {
            continue;
        }

        num = ndata->num_job_slot - ndata->num_reserving_slot;

        LIST_ITERATOR_T iter;
        gf_listiterator_link(&iter, ndata->started_jobs);

        LIST_PROXY_T *pxy;
        for (pxy = (LIST_PROXY_T *)gf_listiterator_curentry(&iter);
             !gf_listiterator_isend(&iter) && 0<num;
             gf_listiterator_getnext(&iter, (LIST_T **)&pxy)) {

            if (NULL == pxy->subject) {
                continue;
            }

            struct job *loopJob;
            loopJob = (struct job *)pxy->subject;

            if (NULL == loopJob->start_info) {
                continue;
            }

            unsigned int numSlot = 0;
            unsigned int k;
            for (k = 0; k < loopJob->start_info->number_exec_node; k++) {
                if (ndata == loopJob->start_info->exec_nodes[k].enode) {
                    numSlot += loopJob->start_info->exec_nodes[k].number_slot;
                    break;
                }
            }

            if (0 == numSlot) {
                continue;
            }

            if (totalRunJobs == tableSize) {

                tableSize *= 2;
                runlimitJob = (struct jobRemainTime *)realloc(runlimitJob,
                                                              tableSize*sizeof(struct jobRemainTime));
                if (NULL == runlimitJob) {
                    log_message(ERR, NOCLASS, STR_FUNC_D_FAIL_M, __func__,
                                "calloc", tableSize*sizeof(struct jobRemainTime));
                    return;
                }
            }

            num -= numSlot;

            int runLimit;
            runLimit = (int)RUN_LIMIT_OF_JOB(loopJob);
            if (0 >= runLimit) {
                continue;
            }

            eligible += numSlot;

            runlimitJob[totalRunJobs].remain_time = runLimit - loopJob->start_info->running_time;
            runlimitJob[totalRunJobs].num_slot = numSlot;

            totalRunJobs++;
        }
    }
    gf_hash_walk_end(&walk);

    if (0 == eligible) {

        FREEUP(runlimitJob);

        if (gf_get_logclass() & SCHEDULE) {
            log_message(DEBUG, SCHEDULE, "%s: can't find enough slot from reserving jobs for job <%s> to backfill.",
                        __func__, jobid_2string(reservejob->jobid, strJobId));
        }

        return;
    } else {
        eligible = 0;
    }

    qsort((struct jobRemainTime *)runlimitJob, totalRunJobs, sizeof(struct jobRemainTime),
          compare_lefttime);

    i = 0;
    for (i = 0; i < totalRunJobs; i++) {

        eligible += runlimitJob[i].num_slot;

        if (eligible >= needed) {
            reservejob->possible_start = sessiontime + runlimitJob[i].remain_time;
            break;
        }
    }

    if (0 == reservejob->possible_start && 0 < eligible) {
        reservejob->possible_start = sessiontime + runlimitJob[i-1].remain_time;
    }
    FREEUP(runlimitJob);

    return;
} // end function setjob_starttime

/**
 * @brief       policy: create reservation job list for backfill
 *
 * @param[in]   rsvjob         #1: reservation job
 * @param[in]   bfslot         #2: number of slot for backfill
 *
 * @retval      not NULL       #1: succeed
 * @retval      NULL           #2: failed, not enough memory
 *
 * @note        Put reservation job to a list for backfill.
 */
LIST_T *
new_reservation_list(struct job *rsvjob, unsigned int bfslot)
{
    struct reservation *bfInfo;
    bfInfo = (struct reservation *)calloc(1, sizeof(struct reservation));
    if (NULL == bfInfo) {
        log_message(ERR, NOCLASS, STR_FUNC_D_FAIL_M, __func__,
                    "calloc", sizeof(struct reservation));
        return NULL;
    }

    bfInfo->bf_nodes = (struct executeNode *)calloc(rsvjob->start_info->number_exec_node,
                                                            sizeof(struct executeNode));
    if (NULL == bfInfo->bf_nodes) {
        log_message(ERR, NOCLASS, STR_FUNC_D_FAIL_M, __func__,
                    "calloc", rsvjob->start_info->number_exec_node*sizeof(struct executeNode));
        return NULL;
    }

    unsigned int j;
    for (j=0; j<rsvjob->start_info->number_exec_node; j++) {
        bfInfo->bf_nodes[j].enode = rsvjob->start_info->exec_nodes[j].enode;
        bfInfo->bf_nodes[j].number_slot = rsvjob->start_info->exec_nodes[j].number_slot;
    }
    bfInfo->num_bf_node = rsvjob->start_info->number_exec_node;
    bfInfo->backfillee_job = rsvjob;
    bfInfo->num_bf_slot = bfslot;

    LIST_T *reservationList;
    reservationList = gf_list_make("the backfill list");
    if (NULL == reservationList) {
        return NULL;
    }

    gf_list_insert(reservationList, reservationList, (LIST_T *)bfInfo);

    return reservationList;
} // end function new_reservation_list

LIST_T *
dup_reservation(LIST_T *src)
{
    LIST_T *list;

    list = gf_list_duplicate(src, sizeof(struct reservation));

    return list;
}

/**
 * @brief       policy: redo reservation for job due to dispatching a backfill job
 *
 * @param[in|out]   reservationlist   #1: reservation job list
 */
void
redo_reservation(LIST_T *reservationlist)
{
    if (NULL == reservationlist) {
        return;
    }

    LIST_ITERATOR_T iter;
    gf_listiterator_link(&iter, reservationlist);

    struct reservation *reserve;
    for (reserve = (struct reservation *)gf_listiterator_curentry(&iter);
         !gf_listiterator_isend(&iter);
         gf_listiterator_getnext(&iter, (LIST_T **)&reserve)) {

        struct job *job = reserve->backfillee_job;

        if (NULL != job->start_info && 0 < job->start_info->number_exec_node) {
            free_reserve_node(job);
        }

        if (NULL == job->start_info) {
            job->start_info = (struct startedInfo *)calloc(1, sizeof(struct startedInfo));
            if (NULL == job->start_info) {
                log_message(ERR, NOCLASS, STR_FUNC_D_FAIL_M, __func__,
                            "calloc", sizeof(struct startedInfo));
                return;
            }
        }

        job->start_info->number_exec_node = reserve->num_bf_node;
        job->start_info->exec_nodes = reserve->bf_nodes;

        reserve->bf_nodes = NULL;
        reserve->num_bf_node = 0;

        reserve_4job(job);
    }

    return;
} // end function redo_reservation

/**
 * @brief       policy: get slots for backfill job
 *
 * @param[in]   bfjob          #1: backfill job
 * @param[in]   sessiontime    #2: schedule begin time
 *
 * @note        Go through reservation job list to get slots for backfill job.
 */
void
backfill_job(struct job *bfjob, time_t sessiontime)
{
    LIST_T *reserveJobs;
    reserveJobs = gf_list_make("backfill list");

    order_reservation_job(bfjob, reserveJobs, sessiontime);

    struct backfillReadyNode *bfNodes;
    bfNodes = (struct backfillReadyNode *)calloc(bfjob->num_ready_node,
                                                 sizeof(struct backfillReadyNode));
    if (NULL == bfNodes) {
        log_message(ERR, NOCLASS, STR_FUNC_D_FAIL_M, __func__,
                    "calloc", bfjob->num_ready_node*sizeof(struct backfillReadyNode));
        return;
    }

    unsigned int numBackfillNode=0, i;
    struct readyNode *dispatchNodes;
    dispatchNodes = (struct readyNode *)calloc(bfjob->num_ready_node, sizeof(struct readyNode));
    if (NULL == dispatchNodes) {
        log_message(ERR, NOCLASS, STR_FUNC_D_FAIL_M, __func__,
                    "calloc", bfjob->num_ready_node*sizeof(struct readyNode));
        return;
    }

    int nSlots, nAvailSlots;

    LIST_ITERATOR_T iter;
    gf_listiterator_link(&iter, reserveJobs);

    struct reservation *reserve, *nextReserve;
    for (reserve = (struct reservation *)gf_listiterator_curentry(&iter);
         !gf_listiterator_isend(&iter) && bfjob->num_dispatch_slot < bfjob->num_free_slot
         && bfjob->num_dispatch_slot < bfjob->shared->submit.max_job_slot;
         reserve = nextReserve) {

        int numBackfillSlot;
        numBackfillSlot = MIN(reserve->num_bf_slot,
                              bfjob->shared->submit.max_job_slot - bfjob->num_dispatch_slot);

        for (i=0; i<numBackfillNode; i++) {

            if (reserve->node_index == bfNodes[i].node_index) {
                break;
            }
        }

        int maxSlots, slotsToUse;
        maxSlots = bfjob->ready_nodes[reserve->node_index].number_free_slot;
        slotsToUse = MIN(maxSlots, numBackfillSlot);

        if (i == numBackfillNode) {

            bfNodes[i].number_free_slot = slotsToUse;
            bfNodes[i].node_index = reserve->node_index;
            numBackfillNode ++;
        } else {

            slotsToUse = MIN(slotsToUse,  maxSlots - bfNodes[i].number_free_slot);
            bfNodes[i].number_free_slot += slotsToUse;
        }
        reserve->num_bf_slot = slotsToUse;

        bfNodes[i].total_slot = bfNodes[i].number_free_slot;

        gf_listiterator_getnext(&iter, (LIST_T **)&nextReserve);
        gf_list_remove(reserveJobs, (LIST_T *)reserve);

        if (NULL == bfNodes[i].bfjob_list) {
            bfNodes[i].bfjob_list = gf_list_make("backfill list");
        }

        if (slotsToUse != 0) {
            gf_list_insert(bfNodes[i].bfjob_list, bfNodes[i].bfjob_list, (LIST_T *)reserve);
        } else {
            FREEUP(reserve);
        }

        bfjob->num_dispatch_slot += slotsToUse;
    }
    gf_list_free(reserveJobs, NULL);

    if (bfjob->num_dispatch_slot < bfjob->num_free_slot
        && bfjob->num_dispatch_slot < bfjob->shared->submit.max_job_slot) {

        for (i=0; i<numBackfillNode && bfjob->num_dispatch_slot<bfjob->num_free_slot
                  && bfjob->num_dispatch_slot<bfjob->shared->submit.max_job_slot; i++) {

            int index = bfNodes[i].node_index;
            nAvailSlots = MIN(bfjob->ready_nodes[index].number_free_slot-bfNodes[i].number_free_slot,
                              bfjob->shared->submit.max_job_slot - bfjob->num_dispatch_slot);
            if (0 == nAvailSlots) {
                continue;
            }

            bfNodes[i].number_free_slot += nAvailSlots;
            bfNodes[i].total_slot = bfNodes[i].number_free_slot;
            bfjob->num_dispatch_slot += nAvailSlots;
        }
    }

    if (bfjob->num_dispatch_slot < bfjob->num_free_slot
        && bfjob->num_dispatch_slot < bfjob->shared->submit.max_job_slot) {

        for (i=0; i<bfjob->num_ready_node
                  && bfjob->num_dispatch_slot<bfjob->num_free_slot
                  && bfjob->num_dispatch_slot<bfjob->shared->submit.max_job_slot;
             i++) {

            if (isin_backfill_readynode(bfNodes, numBackfillNode, i)) {
                continue;
            }

            if (0 == bfjob->ready_nodes[i].number_free_slot) {
                continue;
            }

            nAvailSlots = MIN(bfjob->ready_nodes[i].number_free_slot,
                              bfjob->shared->submit.max_job_slot - bfjob->num_dispatch_slot);
            bfNodes[numBackfillNode].number_free_slot = nAvailSlots;
            bfNodes[numBackfillNode].total_slot = nAvailSlots;
            bfNodes[numBackfillNode].node_index = i;
            bfjob->num_dispatch_slot += nAvailSlots;
            numBackfillNode ++;
        }
    }

    if (bfjob->num_dispatch_slot < bfjob->shared->submit.num_job_slot) {

        for (i=0; i<numBackfillNode && bfjob->num_dispatch_slot<bfjob->num_slot
                  && bfjob->num_dispatch_slot<bfjob->shared->submit.num_job_slot; i++) {
            nSlots = MIN(bfjob->ready_nodes[bfNodes[i].node_index].total_slot
                          - bfNodes[i].total_slot,
                         bfjob->shared->submit.max_job_slot - bfjob->num_dispatch_slot);
            if (0 == nSlots) {
                continue;
            }

            bfNodes[i].total_slot += nSlots;
            bfjob->num_dispatch_slot += nSlots;
        }

        if (bfjob->num_dispatch_slot < bfjob->num_slot &&
            bfjob->num_dispatch_slot < bfjob->shared->submit.num_job_slot) {

            for (i = 0; i < bfjob->num_ready_node
                        && bfjob->num_dispatch_slot<bfjob->num_slot
                        && bfjob->num_dispatch_slot<bfjob->shared->submit.num_job_slot;
                 i++) {

                if (isin_backfill_readynode(bfNodes, numBackfillNode, i)) {
                    continue;
                }

                if (0 == bfjob->ready_nodes[i].total_slot) {
                    continue;
                }

                nSlots = MIN(bfjob->ready_nodes[i].total_slot,
                             bfjob->shared->submit.max_job_slot - bfjob->num_dispatch_slot);

                bfNodes[numBackfillNode].total_slot = nSlots;
                bfNodes[numBackfillNode].number_free_slot = MIN(bfjob->ready_nodes[i].number_free_slot, nSlots);
                bfNodes[numBackfillNode].node_index = i;
                bfjob->num_dispatch_slot += nSlots;
                numBackfillNode ++;
            }
        }
    }

    for (i=0; i<numBackfillNode; i++) {
        dispatchNodes[i].rnode = bfjob->ready_nodes[bfNodes[i].node_index].rnode;
        dispatchNodes[i].total_slot = bfNodes[i].total_slot;
        dispatchNodes[i].number_free_slot = bfNodes[i].number_free_slot;
        dispatchNodes[i].reservation_jobs = bfNodes[i].bfjob_list;

        if (0 < bfjob->shared->submit.num_gpu) {
            find_GPU_index(bfjob, &(dispatchNodes[i]), i);
        }

        if (bfjob->shared->job_req != NULL && bfjob->shared->job_req->num_bind > 0) {
            find_numa_core(bfjob, &(dispatchNodes[i]), i);
        }   
                       
    }
    FREEUP(bfNodes);

    bfjob->num_dispatch_node = numBackfillNode;
    FREEUP(bfjob->dispatch_nodes);
    bfjob->dispatch_nodes = dispatchNodes;
     
    if (bfjob->num_dispatch_slot < bfjob->shared->submit.num_job_slot) {
        rm_backfill_slot(bfjob);
    }

    return;
} // end function backfill_job

/**
 * @brief       policy: get slots for backfill job
 *
 * @param[in]   bfjob          #1: backfill job
 *
 * @note        Go through reservation job list to get slots for backfill job.
 */
void
backfill_job_dispatchnode(struct job *bfjob)
{
    unsigned int i;

    for (i=0; i<bfjob->num_dispatch_node; i++) {

        unsigned int rnodeIdx;
        for (rnodeIdx = 0; rnodeIdx < bfjob->num_ready_node; rnodeIdx++) {
            if (bfjob->dispatch_nodes[i].rnode == bfjob->ready_nodes[rnodeIdx].rnode) {
                break;
            }
        }

        if (NULL == bfjob->ready_nodes[rnodeIdx].reservation_jobs) {
            continue;
        }

        unsigned int nSlots = 0;

        LIST_ITERATOR_T iter;
        gf_listiterator_link(&iter, bfjob->ready_nodes[rnodeIdx].reservation_jobs);

        struct reservation *reserve, *dstReserve;
        for (reserve = (struct reservation *)gf_listiterator_curentry(&iter);
             !gf_listiterator_isend(&iter);
             gf_listiterator_getnext(&iter, (LIST_T **)&reserve)) {

            dstReserve = dup_backfillee(reserve);

            dstReserve->num_bf_slot = MIN(bfjob->dispatch_nodes[i].number_free_slot-nSlots,
                                          dstReserve->num_bf_slot);
            dstReserve->node_index = i;
            nSlots += dstReserve->num_bf_slot;

            if (NULL == bfjob->dispatch_nodes[i].reservation_jobs) {
                bfjob->dispatch_nodes[i].reservation_jobs = gf_list_make("ready node reserve job list");
            }

            gf_list_insert(bfjob->dispatch_nodes[i].reservation_jobs,
                           bfjob->dispatch_nodes[i].reservation_jobs,
                           (LIST_T *)dstReserve);

            if (nSlots == bfjob->dispatch_nodes[i].number_free_slot) {
                break;
            }
        }
    }

    if (bfjob->num_dispatch_slot < bfjob->shared->submit.num_job_slot) {
        rm_backfill_slot(bfjob);
    }

    return;
} // end function backfill_job_dispatchnode

/**
 * @brief       policy: sum up backfill slot of all reservation jobs
 *
 * @param[in]   reservejobs    #1: reservation job list
 *
 * @retval      >0             #1: backfill slot
 * @retval      0              #2: no backfill slot
 *
 * @note        Go through reservation job list to to sum up backfill slot.
 */
int
sum_backfill_slot(LIST_T *reservejobs)
{
    if (NULL == reservejobs) {
        return 0;
    }

    int totalBfSlot = 0;

    LIST_ITERATOR_T iter;
    gf_listiterator_link(&iter, reservejobs);

    struct reservation *reserve;
    for (reserve = (struct reservation *)gf_listiterator_curentry(&iter);
         !gf_listiterator_isend(&iter);
         gf_listiterator_getnext(&iter, (LIST_T **)&reserve)) {

        totalBfSlot += reserve->num_bf_slot;
    }

    return totalBfSlot;
}

static int
compare_lefttime(const void *element1, const void *element2)
{
    struct jobRemainTime *job1, *job2;

    job1 = (struct jobRemainTime *) element1;
    job2 = (struct jobRemainTime *) element2;

    return (job1->remain_time - job2->remain_time);
}

static struct reservation *
dup_backfillee(struct reservation *src)
{
    struct reservation *dst;

    dst = (struct reservation *)calloc(1, sizeof(struct reservation));
    if (NULL == dst) {
        log_message(ERR, NOCLASS, STR_FUNC_D_FAIL_M, __func__,
                    "calloc", sizeof(struct reservation));
        return NULL;
    }

    dst->backfillee_job = src->backfillee_job;
    dst->node_index = src->node_index;
    dst->num_bf_slot = src->num_bf_slot;

    return dst;
}

static void
order_reservation_job(struct job *bfjob, LIST_T *bfjoblist, time_t sessiontime)
{
    unsigned int i;
    for (i=0; i<bfjob->num_ready_node; i++) {

        if (NULL == bfjob->ready_nodes[i].reservation_jobs) {
            continue;
        }

        LIST_ITERATOR_T iter;
        gf_listiterator_link(&iter, bfjob->ready_nodes[i].reservation_jobs);

        struct reservation *reserve;
        for (reserve = (struct reservation *)gf_listiterator_curentry(&iter);
             !gf_listiterator_isend(&iter);
             gf_listiterator_getnext(&iter, (LIST_T **)&reserve)) {

            reserve->node_index = i;

            struct reservation *dstReserve;
            dstReserve = dup_backfillee(reserve);

            LIST_ITERATOR_T iterBackfill;
            struct reservation *entryBackfill;
            int diffItem, diffEntry, finishTimeOnItem, finishTimeOnEntry;

            finishTimeOnItem = sessiontime + RUN_LIMIT_OF_JOB(bfjob);
            diffItem = dstReserve->backfillee_job->possible_start - finishTimeOnItem;

            gf_listiterator_link(&iterBackfill, bfjoblist);

            bool_t inserted = FALSE;
            for (entryBackfill = (struct reservation *)gf_listiterator_curentry(&iterBackfill);
                 !gf_listiterator_isend(&iterBackfill);
                 gf_listiterator_getnext(&iterBackfill, (LIST_T **)&entryBackfill)) {

                finishTimeOnEntry = sessiontime + RUN_LIMIT_OF_JOB(bfjob);
                diffEntry = entryBackfill->backfillee_job->possible_start - finishTimeOnEntry;

                if (diffItem < diffEntry) {

                    gf_list_insert(bfjoblist, (LIST_T *)entryBackfill, (LIST_T *)dstReserve);
                    inserted = TRUE;
                    break;
                }
            }

            if (!inserted) {
                gf_list_insert(bfjoblist, bfjoblist, (LIST_T *)dstReserve);
            }
        }
    }

    return;
} // end function order_reservation_job

static int
isin_backfill_readynode(struct backfillReadyNode *bfreadynodes,
                        unsigned int numnode, unsigned int index)
{
    unsigned int j;
    for (j = 0; j < numnode; j++) {

        if (bfreadynodes[j].node_index == index) {
            return TRUE;
        }
    }

    return FALSE;
}

static void
rm_backfill_slot(struct job *bfjob)
{
    unsigned int totalSlots=0;

    unsigned int i;
    for (i=0; i<bfjob->num_dispatch_node; i++) {

        if (NULL == bfjob->dispatch_nodes[i].reservation_jobs) {
            continue;
        }

        unsigned int rnodeIdx;
        for (rnodeIdx = 0; rnodeIdx < bfjob->num_ready_node; rnodeIdx++) {
            if (bfjob->dispatch_nodes[i].rnode == bfjob->ready_nodes[rnodeIdx].rnode) {
                break;
            }
        }

        LIST_ITERATOR_T iter;
        gf_listiterator_link(&iter, bfjob->dispatch_nodes[i].reservation_jobs);

        struct reservation *reserve;
        for (reserve = (struct reservation *)gf_listiterator_curentry(&iter);
             !gf_listiterator_isend(&iter);
             gf_listiterator_getnext(&iter, (LIST_T **)&reserve)) {

            int numSlotsToRemove, numAvailSlotsToRemove,
                numNonBackfillSlotsUsed, numAvailNonBackfillSlotsUsed,
                numNonBackfillSlotsUnused, numAvailNonBackfillSlotsUnused;

            unsigned int backfillSlots;
            backfillSlots = reserve->num_bf_slot;

            numNonBackfillSlotsUsed = bfjob->dispatch_nodes[i].total_slot - backfillSlots;
            numAvailNonBackfillSlotsUsed = bfjob->dispatch_nodes[i].number_free_slot - backfillSlots;

            numNonBackfillSlotsUnused =
                bfjob->ready_nodes[rnodeIdx].none_bfslot - numNonBackfillSlotsUsed;
            numAvailNonBackfillSlotsUnused =
                bfjob->ready_nodes[rnodeIdx].free_none_bfslot - numAvailNonBackfillSlotsUsed;

            numSlotsToRemove = MAX(0, backfillSlots - numNonBackfillSlotsUnused);
            numAvailSlotsToRemove = MAX(0, backfillSlots - numAvailNonBackfillSlotsUnused);
            bfjob->dispatch_nodes[i].total_slot -= numSlotsToRemove;
            bfjob->dispatch_nodes[i].number_free_slot -= numAvailSlotsToRemove;
            totalSlots += numSlotsToRemove;
        }
    }

    bfjob->num_dispatch_slot -= totalSlots;

    return;
} // end function rm_backfill_slot

#ifdef __cplusplus
}
#endif
